package leetcode.editor.cn.dsa22_segmentTree;

import java.util.Arrays;

/**
 * 线段树
 */
public class SegmentTree {
    int[] value, nums; // value为线段树元素，nums为原数据
    int n; // 原数据长度

    public SegmentTree(int n, int[] nums) {
        value = new int[4 * n]; // 最大为4n空间
        this.n = n;
        this.nums = nums;
        build(0, 0, n-1);
    }
    // 在pos位置创建表示区间[left...right]的线段树，递归算法
    public void build(int pos, int left, int right) {
        if (left == right) {
            value[pos] = nums[left]; // 叶子节点，赋值原数据
            return;
        }
        // 计算分界线，不写成(left+right)/2是因为可能数据会溢出
        int mid = left + (right - left) / 2;
        // 递归构建左子树和右子树
        build(2*pos+1, left, mid);
        build(2*pos+2, mid + 1, right);
        // 合并左右区间的值
        value[pos] = value[2*pos+1] + value[2*pos+2];
    }

    // 在以pos为根的线段树中[left...right]的范围里，搜索区间[qleft...qright]的值
    // 先判断根节点是否完全包含在当前区间，包含则返回当前区间值
    // 否则从左右子树中查出完全包含在查询区间内的所有区间值，累加
    public int query(int pos, int left, int right, int qleft, int qright) {
        if (qleft > right || qright < left) return 0;// 查询区间在当前区间之外
        if (qleft <= left && qright >= right) return value[pos];// 查询区间完全包含当前区间
        int mid = left + (right - left) / 2;
        // 递归查询左子树和右子树
        int leftSum = query(2 * pos + 1, left, mid, qleft, qright);
        int rightSum = query(2 * pos + 2, mid + 1, right, qleft, qright);
        return leftSum + rightSum;
    }
    // 在以pos为根的线段树中更新index的值为val
    public void update(int pos, int left, int right, int index, int val) {
        if (left == right) { // 找到了该元素所在的叶子节点
            value[pos] = val;
            return;
        }
        int mid = left + (right - left) / 2;
        if (index <= mid) // 要更新的节点在左子树
            update(2 * pos + 1, left, mid, index, val);
        else
            update(2 * pos + 2, mid + 1, right, index, val);
        // 目标节点的父亲节点，同样需要进行更新操作
        value[pos] = value[2 * pos + 1] + value[2 * pos + 2];
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {0,1,3,4,6};
        SegmentTree segmentTree = new SegmentTree(arr.length, arr);
        // [14, 4, 10, 1, 3, 4, 6, 0, 1...]
        System.out.println(Arrays.toString(segmentTree.value));
        int query = segmentTree.query(0, 0, 4, 0, 4);
        System.out.println(query); //14
        int query2 = segmentTree.query(0, 0, 4, 2, 3);
        System.out.println(query2); //7
        segmentTree.update(0, 0, 4, 1, 10);
        //[23, 13, 10, 10, 3, 4, 6, 0, 10...]
        System.out.println(Arrays.toString(segmentTree.value));
    }
}
